#include "graph.h"
#include "utils.h"
#include "set.h"
#include "sortstrategy.h"
#include "bubblesort.h"
#include "mergesort.h"
#include "heapsort.h"
#include "stdsort.h"
#include "algostrategy.h"
#include "prims.h"
#include "algo.h"

#include <stdio.h>


using std::vector;

// Doing the sorting as a separate step rather than using a priority queue gives a huge hit
// to performance, you'll need to know why for assignment 2
void Prims::compute(vector<Vertex> &vertexVector, List &edgeList, DataStrategy *s)
{
	QueueStrategy* qs = NULL;
	//PriorityQueue queue(type, (size * (size - 1)) / 2);
	qs = dynamic_cast<QueueStrategy*>(s);
	if(!qs)		
	{
		std::cerr << "DataStrategy is not a QueueStrategy" << std::endl;
		exit(EXIT_FAILURE);
	}
	
	
#if SHOWEDGES
	int edgecount = 0;
	int maxedgecount = 0;
#endif	

	PriorityQueue queue(qs);	
	int size = (int) vertexVector.size();
	
	// As with Sets, a visited flag could be made a member of the vertex class,
	// however an array of flags is used instead for the same modularity reasons
	// as with Kruskal's
	bool visitedFlags[size];
	for (int i = 0; i < size; i++)
		visitedFlags[i] = false;

	int currPos = 0, mstSize = 1;
	while (mstSize < size)
	{
		if (!visitedFlags[currPos])
			for (int i = 0; i < size; i++)
				if (i == currPos)
					continue;
				else if (!visitedFlags[i])
				{
					queue.insert(Edge(vertexVector[currPos], vertexVector[i], currPos, i));
					
#if SHOWEDGES		
					edgecount++;
					if (edgecount > maxedgecount)
						maxedgecount = edgecount;
#endif					
				}
		visitedFlags[currPos] = true;		
		Edge minEdge = queue.deleteMin();		
#if SHOWEDGES
		edgecount--;
		printf("No. edges in priority queue: %d\n", edgecount);
#endif	

		int index1 = minEdge.index1;
		int index2 = minEdge.index2;
		if (!visitedFlags[index2])
		{
			currPos = index2;
			edgeList.add(vertexVector[index1].p, vertexVector[index2].p, index1, index2);
			mstSize++;
		}
	}

#if SHOWEDGES		
		printf("Maxnumber edges was: %d\n", maxedgecount);
#endif	
	
}
